package 贪心算法;

import java.util.Arrays;
import java.util.PriorityQueue;

public class IPO {

    //正常贪心
    public static int findMaximizedCapital1(int k, int w, int[] profits, int[] capital) {
        boolean speedUp = true;
        for (int c: capital){
            if (w < c) {
                speedUp = false;
            }
        }
        if (speedUp) {
            PriorityQueue<Integer> heap = new PriorityQueue<>();
            for (int p: profits) {
                heap.add(p);
                if (heap.size() > k) heap.poll();
            }
            for (int h: heap) w += h;
            return w;
        }

        int n = profits.length;
        int[][] pc = new int[n][2];
        for (int i = 0; i < n; i++) {
            pc[i][0] = profits[i];
            pc[i][1] = capital[i];
        }
        Arrays.sort(pc,(a1,a2)->a2[0] - a1[0]);

        for (int i = 0; i < Math.min(k, n); i++) {
            boolean flag = false;
            for (int j = 0; j < n; j++) {
                if (pc[j][1] <= w){
                    flag = true;
                    pc[j][1] = Integer.MAX_VALUE;
                    w+= pc[j][0];
                    break;
                }
            }
            if (!flag){
                break;
            }

        }

        return w;
    }

    //双堆加贪心
    public static int findMaximizedCapital(int k, int w, int[] profits, int[] capital) {
        boolean speedUp = true;
        for (int c: capital){
            if (w < c) {
                speedUp = false;
            }
        }
        if (speedUp) {
            PriorityQueue<Integer> heap = new PriorityQueue<>();
            for (int p: profits) {
                heap.add(p);
                if (heap.size() > k) heap.poll();
            }
            for (int h: heap) w += h;
            return w;
        }
        int n = profits.length;
        PriorityQueue<int[]> capitalMinHeap = new PriorityQueue<>((a1,a2)->a1[0]-a2[0]);
        for (int i = 0; i < n; i++) {
            capitalMinHeap.add(new int[]{capital[i],profits[i]});
        }

        PriorityQueue<Integer>  profitsMaxHeap = new PriorityQueue<>((x,y)->y-x);
        for (int i = 0; i < k; i++) {
            while (!capitalMinHeap.isEmpty() && capitalMinHeap.peek()[0] <= w){
                profitsMaxHeap.add(capitalMinHeap.poll()[1]);
            }
            if (profitsMaxHeap.isEmpty()){
                break;
            }
            w += profitsMaxHeap.poll();
        }
        return w;
    }


        public static void main(String[] args) {
        int[] profits = {1,2,3};
        int[] capital = {0,1,1};
        System.out.println(findMaximizedCapital(2,0,profits,capital));
    }
}
